//
// Created by francklinson on 2021/5/6.
//

/*
给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。


示例 1：

输入：S = "ab#c", T = "ad#c"
输出：true
解释：S 和 T 都会变成 “ac”。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/backspace-string-compare
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
#include <string>
#include <iostream>
#include <stack>

using namespace std;

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        stack<char> s1;
        stack<char> s2;
        for (const auto &x:s) {
            if (x == '#') {
                if (!s1.empty()) s1.pop();
            } else s1.push(x);
        }
        for (const auto &x:t) {
            if (x == '#') {
                if (!s2.empty()) s2.pop();
            } else s2.push(x);
        }
        while (!s1.empty() and !s2.empty()) {
            if (s1.top() != s2.top()) return false;
            s1.pop();
            s2.pop();
        }
        return (s1.empty() and s2.empty());
    }
};
class Solution2 { // string 自己可以push_back 和 pop_back 不需要额外的stack
public:
    bool backspaceCompare(string S, string T) {
        return build(S) == build(T);
    }

    string build(const string& str) {
        string ret;
        for (char ch : str) {
            if (ch != '#') {
                ret.push_back(ch);
            } else if (!ret.empty()) {
                ret.pop_back();
            }
        }
        return ret;
    }
};

class Solution3 { // 题解 双指针
public:
    bool backspaceCompare(string S, string T) {
        /**
         * 一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。
         * 因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。
        具体地，我们定义 skip 表示当前待删除的字符的数量。每次我们遍历到一个字符：
        若该字符为退格符，则我们需要多删除一个普通字符，我们让 skip 加 1；
        若该字符为普通字符：
        若 skip 为 0，则说明当前字符不需要删去；
        若skip 不为 0，则说明当前字符需要删去，我们让skip 减 1。
        这样，我们定义两个指针，分别指向两字符串的末尾。每次我们让两指针逆序地遍历两字符串，
        直到两字符串能够各自确定一个字符，然后将这两个字符进行比较。
        重复这一过程直到找到的两个字符不相等，或遍历完字符串为止。
         */
        int i = S.length() - 1, j = T.length() - 1;
        int skipS = 0, skipT = 0;

        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (S[i] == '#') {
                    skipS++, i--;
                } else if (skipS > 0) {
                    skipS--, i--;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                if (T[j] == '#') {
                    skipT++, j--;
                } else if (skipT > 0) {
                    skipT--, j--;
                } else {
                    break;
                }
            }
            if (i >= 0 && j >= 0) {
                if (S[i] != T[j]) {
                    return false;
                }
            } else {
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--, j--;
        }
        return true;
    }
};


int main() {
    Solution sol;
    cout << (sol.backspaceCompare("ab#c", "ad#c") ? "true" : "false") << endl;
    cout << (sol.backspaceCompare("ab##", "c#d#") ? "true" : "false") << endl;
    cout << (sol.backspaceCompare("a##c", "#a#c") ? "true" : "false") << endl;
    cout << (sol.backspaceCompare("a#c", "b") ? "true" : "false") << endl;
    cout << (sol.backspaceCompare("y#fo##f", "y#f#o##f") ? "true" : "false") << endl;
    return 0;
}